package weekMatch.one_344;

public class LeeCode_04 {
    public static void main(String[] args) {
        System.out.println(minIncrements(7, new int[]{1, 5, 2, 2, 3, 3, 1}));
    }
    private static int minIncrements(int n, int[] cost) {
        int l = 1, r = 2, m = cost.length, ans = 0, i = 2;
        while (r < m){
            i *= 2;
            l = r + 1;
            r = l + i -1;
        }
        while (l >= 0 && l <= r){
            int t = 0;
            if (r == m - 1 || l >= m){
                i /= 2;
                l = l - i;
                r = l + i - 1;
                continue;
            }
            for (int j = l; j <= r; j++) {
                int a1 = cost[r + 1 + t * 2];
                int a2 = cost[r + 1 + t * 2 + 1];
                cost[j] = Math.max(a1, a2) + cost[j];
                ans += Math.abs(a1 - a2);
                t++;
            }
            i /= 2;
            l = l - i;
            r = l + i - 1;
        }
        return ans;
    }
}
